ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpd/doc/ballroom.tex

   1 \section{3928 - Ballroom Lights}
   2 \textbf{Problema:}
   3 Dada una vista superior de una habitaci'on rectangular en la que hay una serie de
   4 luces (fuentes puntuales de luz) y de columnas (cilindros), determinar la porci'on
   5 del per'imetro de la habitaci'on que se encuentra iluminada por las luces.
   6
   7 \subsection{Resoluci\'on}
   8
   9 La soluci'on del problema consiste en calcular los efectos individuales de cada
  10 luz sobre cada columna considerando una 'unica pared, y luego combinarlos de manera
  11 de obtener el resultado total. Para esto, se considera en primer lugar como se
  12 resuelve el caso particular conociendo la ubicaci'on de ambas dentro de la habitaci'on, las
  13 dimensiones de la misma y el radio de la columna.
  14
  15 \begin{figure}[H]
  16 \centering
  17 \includegraphics[width=12cm]{./figuras/ballroom.png}
  18 \caption{Esquema del caso particular (1 columna, 1 luz, 1 pared)}
  19 \end{figure}
  20
  21 Esta situaci'on se resuelve con trigonometr'ia simple: conociendo el radio de la
  22 columna ($|I_{1}C|$) y la distancia entre la luz y el centro de la misma ($|LC|$),
  23 podemos calcular el 'angulo $a$:
  24
  25 $$a = sin^{-1}\frac{|I_{1}C|}{|LC|}$$
  26
  27 Con el 'angulo $a$ resulta sencillo construir las intersecciones con la pared posterior.
  28 Es importante tener en cuenta el caso en que dicha intersecci'on no existe (estamos
  29 tratando con una semirecta de origen $L$), o se encuentra fuera del segmento que
  30 corresponde a la pared.
  31
  32 Finalmente, se calcula el largo del segmento oscurecido por la columna que cae dentro
  33 de la pared. Con este dato, el algoritmo completo es el siguiente:
  34
  35 \begin{algorithm}[H]
  36 \begin{algorithmic}
  37 \caption{Calcular la longitud del perímetro iluminado}
  38 \FOR{cada pared}
  39   \FOR{cada luz}
  40     \FOR{cada columna}
  41         \STATE obtener la zona oscurecida de esta terna
  42     \ENDFOR
  43     \STATE unir todas las sombras de esta luz
  44     \STATE invertir las sombras para obtener las zonas iluminadas de esta luz
  45   \ENDFOR
  46   \STATE unir todas las zonas iluminadas por cada luz
  47   \STATE calcular la longitud iluminada en esta pared
  48 \ENDFOR
  49 \STATE devolver la suma de las longitudes iluminadas sobre cada pared
  50 \end{algorithmic}
  51 \end{algorithm}
  52
  53 \subsubsection{Implementaci'on}
  54
  55 La implementaci'on no tiene mayores particularidades. Nos encontramos con
  56 un problema de error num'erico producto de la utilización valores obtenidos
  57 con las funciones trigonom'etricas. Lo resolvimos utilizando \textbf{long double}
  58 para aumentar la precisi'on de las operaciones.
  59
  60 Muchos de los datos utilizados en el programa son conjuntos de intervalos
  61 que representan una porci'on (eventualmente discontinua) de los segmentos
  62 que corresponden a las paredes. Estos conjuntos se implementaron sobre secuencias.
  63
  64
  65 \subsubsection{Complejidad}
  66
  67 Llamaremos $C$ a la cantidad de columnas y $L$ a la cantidad de luces.
  68
  69 Las operaciones utilizadas por el algoritmo son:
  70 \begin{itemize}
  71 \item \textbf{B'usqueda de puntos de intersecci'on}, que se hace en tiempo constante en el modelo uniforme.
  72 \item \textbf{Uni'on de conjuntos de intervalos}, que se hace en $O(n log(n))$ orden'andolos primero.
  73 \item \textbf{Inversi'on de conjuntos de intervalos}, que se hace en $O(n)$ puesto que ya est'an ordenados.
  74 \item \textbf{C'alculo de la longitud cubierta por el conjunto}, que se hace en $O(n)$ puesto que ya est'an ordenados.
  75 \end{itemize}
  76
  77 Sabemos adem'as que cada columna tiene a lo sumo una sombra sobre cada pared. Por lo tanto,
  78 unir todas las sombras de una luz se hace en $O(C log(C))$. En peor caso, el conjunto
  79 resultante tiene $C$ elementos, lo que corresponde al caso en que todas las sombras
  80 de las columnas son disjuntas.
  81
  82 La inversi'on se hace entonces en $O(C)$. Para los 'ultimos pasos del ciclo sobre las luces,
  83 se unen las sombras de cada una de ellas. Dado que en peor caso tenemos $L * C$ intervalos
  84 a unir, la uni'on resulta en un costo de $O(LC log(LC))$, seguido del c'alculo de la
  85 longitud en tiempo lineal con un costo de $O(LC)$ dado que tras la uni'on el conjunto
  86 de intervalos se encuentra ordenado.
  87
  88 Estas operaciones se hacen para cada pared, con un total de 4 que no afecta la complejidad
  89 puesto que es constante. Finalmente, el algoritmo tiene un costo de $O(LC log(LC))$, que es
  90 polinomial en el tama~no de la entrada puesto que la misma tiene tama\~no $O(L+C+t)$ (con
  91 $t=log_2(max(ancho, alto))$).
  92
  93 \subsection{Implementación}
  94
  95 \noindent
  96 \ttfamily
  97 \shorthandoff{"}\\
  98 \hlstd{}\hlline{\ 1\ }\hldir{\#include\ $<$iostream$>$}\\
  99 \hlline{\ 2\ }\hlstd{}\hldir{\#include\ $<$cmath$>$}\\
 100 \hlline{\ 3\ }\hlstd{}\hldir{\#include\ $<$cstdio$>$}\\
 101 \hlline{\ 4\ }\hlstd{}\hldir{\#include\ $<$list$>$}\\
 102 \hlline{\ 5\ }\hlstd{}\hldir{\#include\ $<$utility$>$}\\
 103 \hlline{\ 6\ }\hlstd{}\hldir{\#include\ $<$cstdlib$>$}\\
 104 \hlline{\ 7\ }\hlstd{}\hldir{\#include\ $<$cassert$>$}\\
 105 \hlline{\ 8\ }\hlstd{}\hldir{\#include\ $<$complex$>$}\\
 106 \hlline{\ 9\ }\hlstd{}\\
 107 \hlline{10\ }\hldir{\#define\ forn(i,\ n)\ for\ (int\ i\ =\ 0;\ i\ $<$\ (n);\ i++)}\\
 108 \hlline{11\ }\hlstd{}\hldir{\#define\ TOLERANCIA\ 1e{-}8}\\
 109 \hlline{12\ }\hlstd{}\\
 110 \hlline{13\ }\hlkwa{using\ namespace\ }\hlstd{std}\hlsym{;}\\
 111 \hlline{14\ }\hlstd{}\\
 112 \hlline{15\ }\hlkwb{struct\ }\hlstd{MaybeDouble\ }\hlsym{\{}\\
 113 \hlline{16\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{valor}\hlsym{;}\\
 114 \hlline{17\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{bool\ }\hlstd{valido}\hlsym{;}\\
 115 \hlline{18\ }\hlstd{\\
 116 \hlline{19\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwd{MaybeDouble}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{long\ double\ }\hlstd{v}\hlsym{,\ }\hlstd{}\hlkwb{bool\ }\hlstd{b}\hlsym{):\ }\hlstd{}\hlkwd{valor}\hlstd{}\hlsym{(}\hlstd{v}\hlsym{),\ }\hlstd{}\hlkwd{valido}\hlstd{}\hlsym{(}\hlstd{b}\hlsym{)\ \{\};}\\
 117 \hlline{20\ }\hlstd{}\hlsym{\};}\\
 118 \hlline{21\ }\hlstd{}\\
 119 \hlline{22\ }\hlkwb{struct\ }\hlstd{Vector\ }\hlsym{\{}\\
 120 \hlline{23\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{x}\hlsym{;}\\
 121 \hlline{24\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{y}\hlsym{;}\\
 122 \hlline{25\ }\hlstd{\\
 123 \hlline{26\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{long\ double\ }\hlstd{xi}\hlsym{,\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{yi}\hlsym{):\ }\hlstd{}\hlkwd{x}\hlstd{}\hlsym{(}\hlstd{xi}\hlsym{),\ }\hlstd{}\hlkwd{y}\hlstd{}\hlsym{(}\hlstd{yi}\hlsym{)\ \{\};}\\
 124 \hlline{27\ }\hlstd{\\
 125 \hlline{28\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{}\hlkwd{norma}\hlstd{}\hlsym{()}\hlstd{\ \ }\hlsym{\{}\\
 126 \hlline{29\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{hypot}\hlstd{}\hlsym{(}\hlstd{x}\hlsym{,\ }\hlstd{y}\hlsym{);}\\
 127 \hlline{30\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 128 \hlline{31\ }\hlstd{\\
 129 \hlline{32\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{}\hlkwd{angulo}\hlstd{}\hlsym{()\ \{}\\
 130 \hlline{33\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{atan2}\hlstd{}\hlsym{(}\hlstd{y}\hlsym{,\ }\hlstd{x}\hlsym{);}\\
 131 \hlline{34\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 132 \hlline{35\ }\hlstd{}\\
 133 \hlline{36\ }\hlsym{\};}\\
 134 \hlline{37\ }\hlstd{}\\
 135 \hlline{38\ }\hlkwb{struct\ }\hlstd{Columna\ }\hlsym{\{}\\
 136 \hlline{39\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ posicion}\hlsym{;}\\
 137 \hlline{40\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{radio}\hlsym{;}\\
 138 \hlline{41\ }\hlstd{\\
 139 \hlline{42\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwd{Columna}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{long\ double\ }\hlstd{x}\hlsym{,\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{y}\hlsym{,\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{r}\hlsym{)\ :\ }\hlstd{}\hlkwd{posicion}\hlstd{}\hlsym{(}\hlstd{x}\hlsym{,}\hlstd{y}\hlsym{),\ }\hlstd{}\hlkwd{radio}\hlstd{}\hlsym{(}\hlstd{r}\hlsym{)\ \{\};}\\
 140 \hlline{43\ }\hlstd{}\hlsym{\};}\\
 141 \hlline{44\ }\hlstd{}\\
 142 \hlline{45\ }\hlkwc{typedef\ }\hlstd{Vector\ Lampara}\hlsym{;}\\
 143 \hlline{46\ }\hlstd{}\hlkwc{typedef\ }\hlstd{pair}\hlsym{$<$}\hlstd{}\hlkwb{long\ double}\hlstd{}\hlsym{,\ }\hlstd{}\hlkwb{long\ double}\hlstd{}\hlsym{$>$\ }\hlstd{Intervalo}\hlsym{;}\\
 144 \hlline{47\ }\hlstd{}\hlkwc{typedef\ }\hlstd{pair}\hlsym{$<$}\hlstd{Vector}\hlsym{,\ }\hlstd{Vector}\hlsym{$>$\ }\hlstd{Segmento}\hlsym{;}\\
 145 \hlline{48\ }\hlstd{}\\
 146 \hlline{49\ }\\
 147 \hlline{50\ }\hlkwc{inline\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{}\hlkwd{largo}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Segmento}\hlsym{\&\ }\hlstd{s}\hlsym{)\ \{}\\
 148 \hlline{51\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{s}\hlsym{.}\hlstd{second}\hlsym{.}\hlstd{x\ }\hlsym{{-}\ }\hlstd{s}\hlsym{.}\hlstd{first}\hlsym{.}\hlstd{x}\hlsym{,\ }\hlstd{s}\hlsym{.}\hlstd{second}\hlsym{.}\hlstd{y\ }\hlsym{{-}\ }\hlstd{s}\hlsym{.}\hlstd{first}\hlsym{.}\hlstd{y}\hlsym{).}\hlstd{}\hlkwd{norma}\hlstd{}\hlsym{();}\\
 149 \hlline{52\ }\hlstd{}\hlsym{\}}\\
 150 \hlline{53\ }\hlstd{}\\
 151 \hlline{54\ }\hlkwc{inline\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{}\hlkwd{largo}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Intervalo}\hlsym{\&\ }\hlstd{i}\hlsym{)\ \{}\\
 152 \hlline{55\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwd{assert}\hlstd{}\hlsym{(}\hlstd{i}\hlsym{.}\hlstd{first\ }\hlsym{$<$=\ }\hlstd{i}\hlsym{.}\hlstd{second}\hlsym{);}\\
 153 \hlline{56\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{i}\hlsym{.}\hlstd{second\ }\hlsym{{-}\ }\hlstd{i}\hlsym{.}\hlstd{first}\hlsym{;}\\
 154 \hlline{57\ }\hlstd{}\hlsym{\}}\\
 155 \hlline{58\ }\hlstd{\\
 156 \hlline{59\ }\\
 157 \hlline{60\ }MaybeDouble\ }\hlkwd{intersect\textunderscore segments}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Segmento}\hlsym{\&\ }\hlstd{s1}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{Segmento}\hlsym{\&\ }\hlstd{s2}\hlsym{)\ \{}\\
 158 \hlline{61\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ p1\ }\hlsym{=\ }\hlstd{s1}\hlsym{.}\hlstd{first}\hlsym{;}\\
 159 \hlline{62\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ p2\ }\hlsym{=\ }\hlstd{s1}\hlsym{.}\hlstd{second}\hlsym{;}\\
 160 \hlline{63\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ p3\ }\hlsym{=\ }\hlstd{s2}\hlsym{.}\hlstd{first}\hlsym{;}\\
 161 \hlline{64\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ p4\ }\hlsym{=\ }\hlstd{s2}\hlsym{.}\hlstd{second}\hlsym{;}\\
 162 \hlline{65\ }\hlstd{\\
 163 \hlline{66\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{den\ }\hlsym{=\ (}\hlstd{p4}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{y}\hlsym{){*}(}\hlstd{p2}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p1}\hlsym{.}\hlstd{x}\hlsym{)\ {-}\ (}\hlstd{p4}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{x}\hlsym{){*}(}\hlstd{p2}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p1}\hlsym{.}\hlstd{y}\hlsym{);}\\
 164 \hlline{67\ }\hlstd{\\
 165 \hlline{68\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{ua\textunderscore num\ }\hlsym{=\ (}\hlstd{p4}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{x}\hlsym{){*}(}\hlstd{p1}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{y}\hlsym{)\ {-}\ (}\hlstd{p4}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{y}\hlsym{){*}(}\hlstd{p1}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{x}\hlsym{);}\\
 166 \hlline{69\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{ub\textunderscore num\ }\hlsym{=\ (}\hlstd{p2}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p1}\hlsym{.}\hlstd{x}\hlsym{){*}(}\hlstd{p1}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{y}\hlsym{)\ {-}\ (}\hlstd{p2}\hlsym{.}\hlstd{y}\hlsym{{-}}\hlstd{p1}\hlsym{.}\hlstd{y}\hlsym{){*}(}\hlstd{p1}\hlsym{.}\hlstd{x}\hlsym{{-}}\hlstd{p3}\hlsym{.}\hlstd{x}\hlsym{);}\\
 167 \hlline{70\ }\hlstd{\\
 168 \hlline{71\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{}\hlkwd{fabs}\hlstd{}\hlsym{(}\hlstd{den}\hlsym{)\ $<$\ }\hlstd{TOLERANCIA}\hlsym{)\ \{}\\
 169 \hlline{72\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlslc{//\ Caso\ en\ que\ los\ segmentos\ son\ paralelos}\\
 170 \hlline{73\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{}\hlkwd{fabs}\hlstd{}\hlsym{(}\hlstd{ua\textunderscore num\ }\hlsym{{-}\ }\hlstd{ub\textunderscore num}\hlsym{)\ $<$\ }\hlstd{TOLERANCIA\ }\hlsym{\&\&\ }\hlstd{}\hlkwd{fabs}\hlstd{}\hlsym{(}\hlstd{ub\textunderscore num}\hlsym{)\ $<$\ }\hlstd{TOLERANCIA}\hlsym{)\ \{}\\
 171 \hlline{74\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlslc{//\ Las\ rectas\ son\ coincidentes,\ esto\ no\ deberia\ ocurrir}\\
 172 \hlline{75\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{assert}\hlstd{}\hlsym{(}\hlstd{}\hlkwa{false}\hlstd{}\hlsym{);}\\
 173 \hlline{76\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{MaybeDouble}\hlstd{}\hlsym{((}\hlstd{p1}\hlsym{.}\hlstd{}\hlkwd{norma}\hlstd{}\hlsym{()\ $>$\ }\hlstd{p2}\hlsym{.}\hlstd{}\hlkwd{norma}\hlstd{}\hlsym{()}\hlstd{?\ }\hlnum{0\ }\hlstd{}\hlsym{:\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{),\ }\hlstd{}\hlkwa{true}\hlstd{}\hlsym{);}\\
 174 \hlline{77\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 175 \hlline{78\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{MaybeDouble}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlkwa{false}\hlstd{}\hlsym{);}\\
 176 \hlline{79\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 177 \hlline{80\ }\hlstd{\\
 178 \hlline{81\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{ub\textunderscore num}\hlsym{/}\hlstd{den\ }\hlsym{$>$=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \{}\\
 179 \hlline{82\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{MaybeDouble}\hlstd{}\hlsym{(}\hlstd{ua\textunderscore num}\hlsym{/}\hlstd{den}\hlsym{,\ }\hlstd{}\hlkwa{true}\hlstd{}\hlsym{);}\\
 180 \hlline{83\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 181 \hlline{84\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{MaybeDouble}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlkwa{false}\hlstd{}\hlsym{);}\\
 182 \hlline{85\ }\hlstd{}\hlsym{\}}\\
 183 \hlline{86\ }\hlstd{\\
 184 \hlline{87\ }\\
 185 \hlline{88\ }Intervalo\ }\hlkwd{interseccion\textunderscore intervalos}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Intervalo}\hlsym{\&\ }\hlstd{i1}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{Intervalo}\hlsym{\&\ }\hlstd{i2}\hlsym{)\ \{}\\
 186 \hlline{89\ }\hlstd{\\
 187 \hlline{90\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{d0\ }\hlsym{=\ }\hlstd{}\hlkwd{max}\hlstd{}\hlsym{(}\hlstd{i1}\hlsym{.}\hlstd{first}\hlsym{,\ }\hlstd{i2}\hlsym{.}\hlstd{first}\hlsym{);}\\
 188 \hlline{91\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{d1\ }\hlsym{=\ }\hlstd{}\hlkwd{min}\hlstd{}\hlsym{(}\hlstd{i1}\hlsym{.}\hlstd{second}\hlsym{,\ }\hlstd{i2}\hlsym{.}\hlstd{second}\hlsym{);}\\
 189 \hlline{92\ }\hlstd{\\
 190 \hlline{93\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{d1\ }\hlsym{$<$\ }\hlstd{d0}\hlsym{)\ \{}\\
 191 \hlline{94\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{);}\\
 192 \hlline{95\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 193 \hlline{96\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{d0}\hlsym{,\ }\hlstd{d1}\hlsym{);}\\
 194 \hlline{97\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 195 \hlline{98\ }\hlstd{}\hlsym{\}}\\
 196 \hlline{99\ }\hlstd{\\
 197 \hlline{100\ }\\
 198 \hlline{101\ }Intervalo\ }\hlkwd{rango\textunderscore oscurecido}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{Segmento}\hlsym{\&\ }\hlstd{pared}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{Lampara}\hlsym{\&\ }\hlstd{lampara}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{Columna}\hlsym{\&\ }\hlstd{columna}\hlsym{)\ \{}\\
 199 \hlline{102\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ }\hlkwd{bisectriz}\hlstd{}\hlsym{(}\hlstd{columna}\hlsym{.}\hlstd{posicion}\hlsym{.}\hlstd{x\ }\hlsym{{-}\ }\hlstd{lampara}\hlsym{.}\hlstd{x}\hlsym{,\ }\hlstd{columna}\hlsym{.}\hlstd{posicion}\hlsym{.}\hlstd{y\ }\hlsym{{-}\ }\hlstd{lampara}\hlsym{.}\hlstd{y}\hlsym{);}\\
 200 \hlline{103\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{p\ }\hlsym{=\ }\hlstd{}\hlkwd{asin}\hlstd{}\hlsym{(}\hlstd{columna}\hlsym{.}\hlstd{radio}\hlsym{/}\hlstd{bisectriz}\hlsym{.}\hlstd{}\hlkwd{norma}\hlstd{}\hlsym{());}\\
 201 \hlline{104\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{alpha\ }\hlsym{=\ }\hlstd{bisectriz}\hlsym{.}\hlstd{}\hlkwd{angulo}\hlstd{}\hlsym{();}\\
 202 \hlline{105\ }\hlstd{\\
 203 \hlline{106\ }}\hlstd{\ \ \ \ }\hlstd{Vector\ }\hlkwd{d1}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{cos}\hlstd{}\hlsym{(}\hlstd{alpha\ }\hlsym{+\ }\hlstd{p}\hlsym{),\ }\hlstd{}\hlkwd{sin}\hlstd{}\hlsym{(}\hlstd{alpha\ }\hlsym{+\ }\hlstd{p}\hlsym{));}\\
 204 \hlline{107\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Vector\ }\hlkwd{d2}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{cos}\hlstd{}\hlsym{(}\hlstd{alpha\ }\hlsym{{-}\ }\hlstd{p}\hlsym{),\ }\hlstd{}\hlkwd{sin}\hlstd{}\hlsym{(}\hlstd{alpha\ }\hlsym{{-}\ }\hlstd{p}\hlsym{));}\\
 205 \hlline{108\ }\hlstd{\\
 206 \hlline{109\ }}\hlstd{\ \ \ \ }\hlstd{MaybeDouble\ p1\ }\hlsym{=\ }\hlstd{}\hlkwd{intersect\textunderscore segments}\hlstd{}\hlsym{(}\hlstd{pared}\hlsym{,\ }\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{lampara}\hlsym{,\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{lampara}\hlsym{.}\hlstd{x\ }\hlsym{+\ }\hlstd{d1}\hlsym{.}\hlstd{x}\hlsym{,\ }\hlstd{lampara}\hlsym{.}\hlstd{y\ }\hlsym{+}\Righttorque\\
 207 \hlline{110\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{d1}\hlsym{.}\hlstd{y}\hlsym{)));}\\
 208 \hlline{111\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{MaybeDouble\ p2\ }\hlsym{=\ }\hlstd{}\hlkwd{intersect\textunderscore segments}\hlstd{}\hlsym{(}\hlstd{pared}\hlsym{,\ }\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{lampara}\hlsym{,\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{lampara}\hlsym{.}\hlstd{x\ }\hlsym{+\ }\hlstd{d2}\hlsym{.}\hlstd{x}\hlsym{,\ }\hlstd{lampara}\hlsym{.}\hlstd{y\ }\hlsym{+}\Righttorque\\
 209 \hlline{112\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{d2}\hlsym{.}\hlstd{y}\hlsym{)));}\\
 210 \hlline{113\ }\hlstd{\\
 211 \hlline{114\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{unidad\ }\hlsym{=\ }\hlstd{}\hlkwd{largo}\hlstd{}\hlsym{(}\hlstd{pared}\hlsym{);}\\
 212 \hlline{115\ }\hlstd{\\
 213 \hlline{116\ }}\hlstd{\ \ \ \ }\hlstd{}\hlslc{//\ Se\ sabe\ que\ los\ puntos\ de\ interseccion\ estan\ ordenados\ correctamente}\\
 214 \hlline{117\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlslc{//\ porque\ el\ angulo\ de\ diferencia\ entre\ las\ semirectas\ es\ menor\ a\ 180,}\\
 215 \hlline{118\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlslc{//\ entonces\ no\ es\ necesario\ chequearlo.}\\
 216 \hlline{119\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Intervalo\ res}\hlsym{;}\\
 217 \hlline{120\ }\hlstd{\\
 218 \hlline{121\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!}\hlstd{p1}\hlsym{.}\hlstd{valido}\hlsym{)\ \{}\\
 219 \hlline{122\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!}\hlstd{p2}\hlsym{.}\hlstd{valido}\hlsym{)\ \{}\\
 220 \hlline{123\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{);}\\
 221 \hlline{124\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 222 \hlline{125\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{res\ }\hlsym{=\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{p2}\hlsym{.}\hlstd{valor}\hlsym{);}\\
 223 \hlline{126\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 224 \hlline{127\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 225 \hlline{128\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!}\hlstd{p2}\hlsym{.}\hlstd{valido}\hlsym{)\ \{}\\
 226 \hlline{129\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{res\ }\hlsym{=\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{p1}\hlsym{.}\hlstd{valor}\hlsym{,\ }\hlstd{}\hlnum{1}\hlstd{}\hlsym{);}\\
 227 \hlline{130\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 228 \hlline{131\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{res\ }\hlsym{=\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{p1}\hlsym{.}\hlstd{valor}\hlsym{,\ }\hlstd{p2}\hlsym{.}\hlstd{valor}\hlsym{);}\\
 229 \hlline{132\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 230 \hlline{133\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 231 \hlline{134\ }\hlstd{\\
 232 \hlline{135\ }}\hlstd{\ \ \ \ }\hlstd{res\ }\hlsym{=\ }\hlstd{}\hlkwd{interseccion\textunderscore intervalos}\hlstd{}\hlsym{(}\hlstd{res}\hlsym{,\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,}\hlstd{}\hlnum{1}\hlstd{}\hlsym{));}\\
 233 \hlline{136\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{res}\hlsym{.}\hlstd{first\ }\hlsym{{*}\ }\hlstd{unidad}\hlsym{,\ }\hlstd{res}\hlsym{.}\hlstd{second\ }\hlsym{{*}\ }\hlstd{unidad}\hlsym{);}\\
 234 \hlline{137\ }\hlstd{}\hlsym{\}}\\
 235 \hlline{138\ }\hlstd{}\\
 236 \hlline{139\ }\hlkwb{void\ }\hlstd{}\hlkwd{invertir\textunderscore rango}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\&\ }\hlstd{ints}\hlsym{,\ }\hlstd{}\hlkwb{long\ double\ }\hlstd{fin}\hlsym{,\ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\&\ }\hlstd{out}\hlsym{)\ \{}\\
 237 \hlline{140\ }\hlstd{\\
 238 \hlline{141\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!}\hlstd{ints}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{())\ \{}\\
 239 \hlline{142\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,}\hlstd{fin}\hlsym{));}\\
 240 \hlline{143\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{return}\hlstd{}\hlsym{;}\\
 241 \hlline{144\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 242 \hlline{145\ }\hlstd{\\
 243 \hlline{146\ }\\
 244 \hlline{147\ }}\hlstd{\ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ it\ }\hlsym{=\ }\hlstd{ints}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();}\\
 245 \hlline{148\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{it}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$>$\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)\ \{}\\
 246 \hlline{149\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{it}\hlsym{{-}$>$}\hlstd{first}\hlsym{));}\\
 247 \hlline{150\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 248 \hlline{151\ }\hlstd{\\
 249 \hlline{152\ }}\hlstd{\ \ \ \ }\hlstd{it}\hlsym{++;}\\
 250 \hlline{153\ }\hlstd{\\
 251 \hlline{154\ }}\hlstd{\ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ itprev\ }\hlsym{=\ }\hlstd{ints}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();}\\
 252 \hlline{155\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{it\ }\hlsym{!=\ }\hlstd{ints}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{())\ \{}\\
 253 \hlline{156\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{itprev}\hlsym{{-}$>$}\hlstd{second}\hlsym{,\ }\hlstd{it}\hlsym{{-}$>$}\hlstd{first}\hlsym{));}\\
 254 \hlline{157\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{it}\hlsym{++;}\\
 255 \hlline{158\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{itprev}\hlsym{++;}\\
 256 \hlline{159\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 257 \hlline{160\ }\hlstd{\\
 258 \hlline{161\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{itprev}\hlsym{{-}$>$}\hlstd{second\ }\hlsym{$<$\ }\hlstd{fin}\hlsym{)\ \{}\\
 259 \hlline{162\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{itprev}\hlsym{{-}$>$}\hlstd{second}\hlsym{,\ }\hlstd{fin}\hlsym{));}\\
 260 \hlline{163\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 261 \hlline{164\ }\hlstd{}\hlsym{\}}\\
 262 \hlline{165\ }\hlstd{}\\
 263 \hlline{166\ }\\
 264 \hlline{167\ }\hlkwb{void\ }\hlstd{}\hlkwd{reduce\textunderscore union}\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\&\ }\hlstd{l\textunderscore o}\hlsym{,\ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\&\ }\hlstd{out}\hlsym{)\ \{}\\
 265 \hlline{168\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlslc{//\ elimino\ repetidos\ para\ acelerar\ el\ sort}\\
 266 \hlline{169\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{l}\hlsym{;}\\
 267 \hlline{170\ }\hlstd{\\
 268 \hlline{171\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ itcito\ }\hlsym{=\ }\hlstd{l\textunderscore o}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();\ }\hlstd{itcito\ }\hlsym{!=\ }\hlstd{l\textunderscore o}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{();\ }\hlstd{itcito}\hlsym{++)\ \{}\\
 269 \hlline{172\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{itcito}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$<$\ }\hlstd{itcito}\hlsym{{-}$>$}\hlstd{second}\hlsym{)\ \{}\\
 270 \hlline{173\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{l}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{itcito}\hlsym{{-}$>$}\hlstd{first}\hlsym{,\ }\hlstd{itcito}\hlsym{{-}$>$}\hlstd{second}\hlsym{));}\\
 271 \hlline{174\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ if\ }\hlstd{}\hlsym{(}\hlstd{itcito}\hlsym{{-}$>$}\hlstd{first\ }\hlsym{$>$\ }\hlstd{itcito}\hlsym{{-}$>$}\hlstd{second}\hlsym{)\ \{}\\
 272 \hlline{175\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{assert}\hlstd{}\hlsym{(}\hlstd{}\hlkwa{false}\hlstd{}\hlsym{);}\\
 273 \hlline{176\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 274 \hlline{177\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 275 \hlline{178\ }\hlstd{\\
 276 \hlline{179\ }\\
 277 \hlline{180\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!}\hlstd{l}\hlsym{.}\hlstd{}\hlkwd{size}\hlstd{}\hlsym{())\ }\hlstd{}\hlkwa{return}\hlstd{}\hlsym{;}\\
 278 \hlline{181\ }\hlstd{\\
 279 \hlline{182\ }}\hlstd{\ \ \ \ }\hlstd{l}\hlsym{.}\hlstd{}\hlkwd{sort}\hlstd{}\hlsym{();}\\
 280 \hlline{183\ }\hlstd{\\
 281 \hlline{184\ }}\hlstd{\ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ it\ }\hlsym{=\ }\hlstd{l}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();}\\
 282 \hlline{185\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Intervalo\ cand\ }\hlsym{=\ {*}}\hlstd{it}\hlsym{;}\\
 283 \hlline{186\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{Intervalo\ otro}\hlsym{;}\\
 284 \hlline{187\ }\hlstd{\\
 285 \hlline{188\ }}\hlstd{\ \ \ \ }\hlstd{it}\hlsym{++;}\\
 286 \hlline{189\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{while\ }\hlstd{}\hlsym{(}\hlstd{it\ }\hlsym{!=\ }\hlstd{l}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{())\ \{}\\
 287 \hlline{190\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{otro\ }\hlsym{=\ {*}}\hlstd{it}\hlsym{;}\\
 288 \hlline{191\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{otro}\hlsym{.}\hlstd{first\ }\hlsym{$<$\ }\hlstd{otro}\hlsym{.}\hlstd{second}\hlsym{)\ \{}\\
 289 \hlline{192\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{otro}\hlsym{.}\hlstd{first\ }\hlsym{$>$\ }\hlstd{cand}\hlsym{.}\hlstd{second}\hlsym{)\ \{}\\
 290 \hlline{193\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{cand}\hlsym{);}\\
 291 \hlline{194\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{cand\ }\hlsym{=\ }\hlstd{otro}\hlsym{;}\\
 292 \hlline{195\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}\ }\hlstd{}\hlkwa{else\ }\hlstd{}\hlsym{\{}\\
 293 \hlline{196\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(}\hlstd{otro}\hlsym{.}\hlstd{second\ }\hlsym{$>$\ }\hlstd{cand}\hlsym{.}\hlstd{second}\hlsym{)\ \{}\\
 294 \hlline{197\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{cand\ }\hlsym{=\ }\hlstd{}\hlkwd{Intervalo}\hlstd{}\hlsym{(}\hlstd{cand}\hlsym{.}\hlstd{first}\hlsym{,\ }\hlstd{otro}\hlsym{.}\hlstd{second}\hlsym{);}\\
 295 \hlline{198\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 296 \hlline{199\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 297 \hlline{200\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 298 \hlline{201\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{it}\hlsym{++;}\\
 299 \hlline{202\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 300 \hlline{203\ }\hlstd{\\
 301 \hlline{204\ }}\hlstd{\ \ \ \ }\hlstd{out}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{cand}\hlsym{);}\\
 302 \hlline{205\ }\hlstd{}\hlsym{\}}\\
 303 \hlline{206\ }\hlstd{}\\
 304 \hlline{207\ }\\
 305 \hlline{208\ }\hlkwb{long\ double\ }\hlstd{}\hlkwd{resolver}\hlstd{}\hlsym{(}\hlstd{}\hlkwb{const\ }\hlstd{list}\hlsym{$<$}\hlstd{Lampara}\hlsym{$>$\&\ }\hlstd{lamparas}\hlsym{,\ }\hlstd{}\hlkwb{const\ }\hlstd{list}\hlsym{$<$}\hlstd{Columna}\hlsym{$>$\&\ }\hlstd{columnas}\hlsym{,\ }\hlstd{}\hlkwb{int\ }\hlstd{max\textunderscore x}\hlsym{,\ }\hlstd{}\hlkwb{int\ }\Righttorque\\
 306 \hlline{209\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{max\textunderscore y}\hlsym{)\ \{}\\
 307 \hlline{210\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Segmento}\hlsym{$>$\ }\hlstd{paredes}\hlsym{;}\\
 308 \hlline{211\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,}\hlstd{}\hlnum{0}\hlstd{}\hlsym{),\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{max\textunderscore y}\hlsym{)));}\\
 309 \hlline{212\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,}\hlstd{max\textunderscore y}\hlsym{),\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{max\textunderscore x}\hlsym{,\ }\hlstd{max\textunderscore y}\hlsym{)));}\\
 310 \hlline{213\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{max\textunderscore x}\hlsym{,}\hlstd{max\textunderscore y}\hlsym{),\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{max\textunderscore x}\hlsym{,\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)));}\\
 311 \hlline{214\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Segmento}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{max\textunderscore x}\hlsym{,}\hlstd{}\hlnum{0}\hlstd{}\hlsym{),\ }\hlstd{}\hlkwd{Vector}\hlstd{}\hlsym{(}\hlstd{}\hlnum{0}\hlstd{}\hlsym{,\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{)));}\\
 312 \hlline{215\ }\hlstd{\\
 313 \hlline{216\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{long\ double\ }\hlstd{total\ }\hlsym{=\ }\hlstd{}\hlnum{0}\hlstd{}\hlsym{;}\\
 314 \hlline{217\ }\hlstd{\\
 315 \hlline{218\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Segmento}\hlsym{$>$::}\hlstd{iterator\ p\ }\hlsym{=\ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();\ }\hlstd{p\ }\hlsym{!=\ }\hlstd{paredes}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{();\ }\hlstd{p}\hlsym{++)\ \{}\\
 316 \hlline{219\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{luces\textunderscore pared}\hlsym{;}\\
 317 \hlline{220\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Lampara}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ l\ }\hlsym{=\ }\hlstd{lamparas}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();\ }\hlstd{l\ }\hlsym{!=\ }\hlstd{lamparas}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{();\ }\hlstd{l}\hlsym{++)\ \{}\\
 318 \hlline{221\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{zonas\textunderscore tapadas}\hlsym{;}\\
 319 \hlline{222\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Columna}\hlsym{$>$::}\hlstd{const\textunderscore iterator\ c\ }\hlsym{=\ }\hlstd{columnas}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();\ }\hlstd{c\ }\hlsym{!=\ }\hlstd{columnas}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{();\ }\hlstd{c}\hlsym{++)\ \{}\\
 320 \hlline{223\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{zonas\textunderscore tapadas}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{rango\textunderscore oscurecido}\hlstd{}\hlsym{({*}}\hlstd{p}\hlsym{,\ {*}}\hlstd{l}\hlsym{,\ {*}}\hlstd{c}\hlsym{));}\\
 321 \hlline{224\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 322 \hlline{225\ }\hlstd{\\
 323 \hlline{226\ }}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{tapadas\textunderscore unidas}\hlsym{;}\\
 324 \hlline{227\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{zona\textunderscore iluminada}\hlsym{;}\\
 325 \hlline{228\ }\hlstd{\\
 326 \hlline{229\ }}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{reduce\textunderscore union}\hlstd{}\hlsym{(}\hlstd{zonas\textunderscore tapadas}\hlsym{,\ }\hlstd{tapadas\textunderscore unidas}\hlsym{);}\\
 327 \hlline{230\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{invertir\textunderscore rango}\hlstd{}\hlsym{(}\hlstd{tapadas\textunderscore unidas}\hlsym{,\ }\hlstd{}\hlkwd{largo}\hlstd{}\hlsym{({*}}\hlstd{p}\hlsym{),\ }\hlstd{zona\textunderscore iluminada}\hlsym{);}\\
 328 \hlline{231\ }\hlstd{\\
 329 \hlline{232\ }}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{luces\textunderscore pared}\hlsym{.}\hlstd{}\hlkwd{splice}\hlstd{}\hlsym{(}\hlstd{luces\textunderscore pared}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{(),\ }\hlstd{zona\textunderscore iluminada}\hlsym{);}\\
 330 \hlline{233\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 331 \hlline{234\ }\hlstd{\\
 332 \hlline{235\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$\ }\hlstd{luces\textunderscore pared\textunderscore unidas}\hlsym{;}\\
 333 \hlline{236\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{reduce\textunderscore union}\hlstd{}\hlsym{(}\hlstd{luces\textunderscore pared}\hlsym{,\ }\hlstd{luces\textunderscore pared\textunderscore unidas}\hlsym{);}\\
 334 \hlline{237\ }\hlstd{\\
 335 \hlline{238\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(}\hlstd{list}\hlsym{$<$}\hlstd{Intervalo}\hlsym{$>$::}\hlstd{iterator\ it\ }\hlsym{=\ }\hlstd{luces\textunderscore pared\textunderscore unidas}\hlsym{.}\hlstd{}\hlkwd{begin}\hlstd{}\hlsym{();\ }\hlstd{it\ }\hlsym{!=\ }\hlstd{luces\textunderscore pared\textunderscore unidas}\hlsym{.}\hlstd{}\hlkwd{end}\hlstd{}\hlsym{(}\Righttorque\\
 336 \hlline{239\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlsym{);\ }\hlstd{it}\hlsym{++)\ \{}\\
 337 \hlline{240\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{total\ }\hlsym{+=\ }\hlstd{}\hlkwd{largo}\hlstd{}\hlsym{({*}}\hlstd{it}\hlsym{);}\\
 338 \hlline{241\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 339 \hlline{242\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 340 \hlline{243\ }\hlstd{\\
 341 \hlline{244\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{return\ }\hlstd{total}\hlsym{;}\\
 342 \hlline{245\ }\hlstd{}\hlsym{\}}\\
 343 \hlline{246\ }\hlstd{}\\
 344 \hlline{247\ }\\
 345 \hlline{248\ }\hlkwb{int\ }\hlstd{}\hlkwd{main}\hlstd{}\hlsym{()\ \{}\\
 346 \hlline{249\ }\hlstd{\\
 347 \hlline{250\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwb{int\ }\hlstd{nl}\hlsym{,\ }\hlstd{nc}\hlsym{,\ }\hlstd{max\textunderscore x}\hlsym{,\ }\hlstd{max\textunderscore y}\hlsym{;}\\
 348 \hlline{251\ }\hlstd{\\
 349 \hlline{252\ }}\hlstd{\ \ \ \ }\hlstd{}\hlkwa{for\ }\hlstd{}\hlsym{(;;)\ \{}\\
 350 \hlline{253\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{scanf}\hlstd{}\hlsym{(}\hlstd{}\hlstr{"\%d\ \%d\ \%d\ \%d"}\hlstd{}\hlsym{,\ \&}\hlstd{nl}\hlsym{,\ \&}\hlstd{nc}\hlsym{,\ \&}\hlstd{max\textunderscore x}\hlsym{,\ \&}\hlstd{max\textunderscore y}\hlsym{);}\\
 351 \hlline{254\ }\hlstd{\\
 352 \hlline{255\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{if\ }\hlstd{}\hlsym{(!(}\hlstd{nl\ }\hlsym{\textbar \textbar \ }\hlstd{nc\ }\hlsym{\textbar \textbar \ }\hlstd{max\textunderscore x\ }\hlsym{\textbar \textbar \ }\hlstd{max\textunderscore y}\hlsym{))\ \{}\\
 353 \hlline{256\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwa{break}\hlstd{}\hlsym{;}\\
 354 \hlline{257\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 355 \hlline{258\ }\hlstd{\\
 356 \hlline{259\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Vector}\hlsym{$>$\ }\hlstd{lamparas}\hlsym{;}\\
 357 \hlline{260\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{list}\hlsym{$<$}\hlstd{Columna}\hlsym{$>$\ }\hlstd{columnas}\hlsym{;}\\
 358 \hlline{261\ }\hlstd{\\
 359 \hlline{262\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwb{int\ }\hlstd{x}\hlsym{,\ }\hlstd{y}\hlsym{,\ }\hlstd{r}\hlsym{;}\\
 360 \hlline{263\ }\hlstd{\\
 361 \hlline{264\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{forn}\hlstd{}\hlsym{(}\hlstd{i}\hlsym{,\ }\hlstd{nl}\hlsym{)\ \{}\\
 362 \hlline{265\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{scanf}\hlstd{}\hlsym{(}\hlstd{}\hlstr{"\%d\ \%d"}\hlstd{}\hlsym{,\ \&}\hlstd{x}\hlsym{,\ \&}\hlstd{y}\hlsym{);}\\
 363 \hlline{266\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{lamparas}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Lampara}\hlstd{}\hlsym{(}\hlstd{x}\hlsym{,}\hlstd{y}\hlsym{));}\\
 364 \hlline{267\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 365 \hlline{268\ }\hlstd{\\
 366 \hlline{269\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{forn}\hlstd{}\hlsym{(}\hlstd{i}\hlsym{,\ }\hlstd{nc}\hlsym{)\ \{}\\
 367 \hlline{270\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{scanf}\hlstd{}\hlsym{(}\hlstd{}\hlstr{"\%d\ \%d\ \%d"}\hlstd{}\hlsym{,\ \&}\hlstd{x}\hlsym{,\ \&}\hlstd{y}\hlsym{,\ \&}\hlstd{r}\hlsym{);}\\
 368 \hlline{271\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ \ \ \ \ }\hlstd{columnas}\hlsym{.}\hlstd{}\hlkwd{push\textunderscore back}\hlstd{}\hlsym{(}\hlstd{}\hlkwd{Columna}\hlstd{}\hlsym{(}\hlstd{x}\hlsym{,\ }\hlstd{y}\hlsym{,\ }\hlstd{r}\hlsym{));}\\
 369 \hlline{272\ }\hlstd{}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlsym{\}}\\
 370 \hlline{273\ }\hlstd{\\
 371 \hlline{274\ }}\hlstd{\ \ \ \ \ \ \ \ }\hlstd{}\hlkwd{printf}\hlstd{}\hlsym{(}\hlstd{}\hlstr{"\%.4Lf}\hlesc{$\backslash$n}\hlstr{"}\hlstd{}\hlsym{,\ }\hlstd{}\hlkwd{resolver}\hlstd{}\hlsym{(}\hlstd{lamparas}\hlsym{,\ }\hlstd{columnas}\hlsym{,\ }\hlstd{max\textunderscore x}\hlsym{,\ }\hlstd{max\textunderscore y}\hlsym{));}\\
 372 \hlline{275\ }\hlstd{}\hlstd{\ \ \ \ }\hlstd{}\hlsym{\}}\\
 373 \hlline{276\ }\hlstd{}\hlsym{\}}\hlstd{}\\
 374 \mbox{}
 375 \normalfont
 376 \shorthandon{"}